Mortonův rozklad

Mortonův rozklad (též Mortonova Z-křivka, Morton scan order, Z-order curve) je prostor vyplňující křivka, která udává lineární pořadí průchodu vícerozměrným prostorem. Jinými slovy mapuje vícerozměrný prostor do jednorozměrného. Poprvé ji v roce 1966 představil zaměstnanec kanadské IBM Guy M. Morton.^[1]

Užití

Své užití má například při indexování vícerozměrných dat (pak je možné použít algoritmy pro indexování dat jednorozměrných) nebo při implementaci průchodu stromem koeficientů vzniklých vlnkovou transformací (viz algoritmus SPIHT). Algoritmy výpočtu této křivky využívají jejího rekurzivního charakteru.

Vlastnosti

Graf Mortonova rozkladu:

je křivka vyplňující prostor
vyplňuje 2D prostor beze zbytku (na rozdíl např. od dračí smyčky)
pro x, y ∈ N⁺ vyplňuje postupně I. kvadrant
nikde se neprotíná
do každé liché hrany směřuje křivka „doprava“ (o jednotku délky v kladném směru osy x)
po každé 4ⁿ. hraně křivka vyplní čtverec o straně n (dokončí n. iteraci) a přesouvá na první pozici čtyřnásobně velkého čtverce, o vektor (1; n)
po každé 2ⁿ⁺¹. hraně křivka dokončí vyplňování čtverce o straně (n div 4) a přesouvá na první pozici stejně velkého čtverce, o vektor (-n div 4; -1). (div = dělení beze zbytku)
to, že výše zmíněné vektory rostou spolu s n, se v grafu jeví hranami neustále se přibližujícími vertikále nebo horizontále a dá se to považovat za prvek ne tolik lahodící oku, kterými většina prostor-vyplňujících křivek netrpí, neboť ty se posunují o jednotkovou délku.

Rekurzivní výpočet

V programovacím jazyku C:

void ezw_xy(int level, int x, int y, int n)
{
	if (0 == level) {
		echo(0, 0, n);
		return;
	}

	if (level > 1) {
		ezw_xy(level‐1, 2*(x ), 2*(y ), n);
		ezw_xy(level‐1, 2*(x+1), 2*(y ), n);
		ezw_xy(level‐1, 2*(x ), 2*(y+1), n);
		ezw_xy(level‐1, 2*(x+1), 2*(y+1), n);
		return;
	}

	echo(x , y , n);
	echo(x+1, y , n);
	echo(x , y+1, n);
	echo(x+1, y+1, n);
}

void ezw(int level)
{
	ezw_xy(level, 0, 0, 1<<level);
}

// pro matici 8×8
ezw(log2(8));

Výpočet bez rekurze

Ve skriptovacím jazyku PHP (nakreslí Mortonovu křivku pro prvních 1024 pozic).

header("Content-type: image/png");
define('STEP',20);
$image=imagecreatetruecolor(640,640);
for($j=$x=$y=0;$j<1024;$j++){
	$oldx=$x; $oldy=$y;
	for($x=$y=$level=$i=0,$n=$j;$n;$i++,$n>>=2){
		$x+=($n&1)<<$level;
		$y+=($n&2?1:0)<<$level;
		if(!(($i>>1)&(($i>>1)-1)))
			$level++;
	}
	imageline($image,STEP/2+$oldx*STEP, STEP/2+$oldy*STEP,
			STEP/2+$x*STEP, STEP/2+$y*STEP, imagecolorallocate($image,255,0,0));
}
imagepng($image);

Odkazy

Reference

↑ Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd.

Související články

Hilbertova křivka

Externí odkazy

Obrázky, zvuky či videa k tématu Mortonův rozklad na Wikimedia Commons
(anglicky) STANN: A library for approximate nearest neighbor search, using Z-order curve Archivováno 20. 4. 2014 na Wayback Machine.
(anglicky) Methods for programming bit interleaving, Sean Eron Anderson, Stanford University

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

[1] Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd.

[1]